package oj;

import java.util.LinkedList;
import java.util.Queue;

/**
 * oj题 225：用队列实现栈
 * 请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。
 * 实现 MyStack 类：
 * void push(int x) 将元素 x 压入栈顶。
 * int pop() 移除并返回栈顶元素。
 * int top() 返回栈顶元素。
 * boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。
 */
public class MyStack {
    private final Queue<Integer> queue1 = new LinkedList<>();
    private final Queue<Integer> queue2 = new LinkedList<>();
    private Queue<Integer> putElements = queue1;
    private Queue<Integer> assist = queue2;

    public MyStack() {

    }

    public void push(int x) {
        putElements.offer(x);
    }

    public int pop() {
        //先把 size - 1 个元素，放到第二个辅助队列中，然后将元素出栈
        int size = putElements.size();
        for(int i = 0;i < size - 1;i++){
            int e = putElements.poll();
            assist.offer(e);
        }
        int ans = putElements.poll();
        Queue<Integer> t = putElements;
        putElements = assist;
        assist = t;
        return ans;
    }

    public int top() {
        int size = putElements.size();
        for(int i = 0;i < size - 1;i++){
            int e = putElements.poll();
            assist.offer(e);
        }
        int ans = putElements.poll();
        assist.offer(ans);
        Queue<Integer> t = putElements;
        putElements = assist;
        assist = t;
        return ans;
    }

    public boolean empty() {
        return putElements.isEmpty();
    }

    public static void main(String[] args) {
        MyStack stack = new MyStack();
        stack.push(1);
        stack.push(2);
        stack.push(3);
        stack.push(4);
        System.out.println(stack.top());        //4
        stack.push(5);
        System.out.println(stack.top());        //5
        stack.push(6);
        System.out.println(stack.pop());        //6
        System.out.println(stack.pop());        //5
        stack.push(7);
        System.out.println(stack.pop());        //7
        System.out.println(stack.pop());        //4
        System.out.println(stack.pop());        //3
        System.out.println(stack.pop());        //2
        System.out.println(stack.pop());        //1

    }
}
